// https://www.lintcode.com/problem/combination-set/

public class Solution {
    /**
     * @param num: a array
     * @param target: a num
     * @return: return all combinations
     */
    public List<Integer> combinationSet(List<Integer> num, int target) {
        // write your code here
        List<Integer> ret = new ArrayList<>();
        dfs(ret, num, target, 0);
        return ret;
        
    }
    
    private void dfs(List<Integer> ret, List<Integer> num, int target, int cur) {
        for (Integer i : num) {
            int tmp = cur;
            cur = cur * 10 + i;
            if (cur < target) {
                ret.add(cur);
                if (cur > 0) {
                    dfs(ret, num, target, cur);
                }
            }
            cur = tmp;
        }
    }
}